import java.util.Arrays;

public class Test {
    public static int[] Bubblesort(int[] array){
        int i = 0;
        int j = 0;

        for ( i = 0; i < array.length-1 ; i++) {

            for ( j = 0; j < array.length-1-i; j++) {
                boolean flg = false;
                
                if(array[j] > array[j+1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    flg = true;
                }
                if( flg == false){
                    break;
                }
            }
        }
                return array;
    }

    public static void main(String[] args) {
        int[] array = {1,5,7,5,4,56,4,456,86,46,5889};
        int[] ret = Bubblesort(array);
        System.out.println(Arrays.toString(ret));


    }
    public static int binerySearch1(int[] array,int key){
        int left = 0;
        int right = array.length-1;
        while(left < right){
            int m = (left + right) / 2;
            if(array[m] < key){
                left = m + 1;
            } else if (array[m] > key) {
                right = m -1;
            }else {
                return array[m];
            }
        }
        return -1;
    }


    public static void main7(String[] args) {
        int [] array = {1,2,3,4,5,6,7,8,9};
        int ret = binerySearch1(array,8);
        System.out.println(ret);

    }
    public static void main6(String[] args) {
        int [] arr = {1,2,3,4,5,6};
        int i = 0;
        int j = arr.length - 1;
        while(i < j){
            while(i < j && arr[i] % 2 != 0){
                i++;
            }
            while(i < j && arr[j] % 2 == 0){
                j--;
            }
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        System.out.println(Arrays.toString(arr));
    }







    public static void main5(String[] args) {

    }
    public static int binerySearch2(int [] array,int key){
        int left = 0;
        int right = array.length-1;
        while(left < right){
            int m = (left + right)/2;

            if(array[m] < key){
               left = m + 1 ;
            } else if(array[m] > key){
                right = m - 1;
            }else {
                return m;
            }
        }
        return -1;

    }

    public static void main4(String[] args) {
        int [] array = {1,2,3,4,5,6,7,8,9};
        int ret = binerySearch2(array,8);
        System.out.println(ret);

    }
    public static int sumArray(int [] array){
        int sum = 0;
        for(int i = 0; i < array.length; i++){
             sum += array [i];
        }
        return sum;
    }

    public static void main3(String[] args) {
        int [] array = {1,2,3,4,5,6};
        int ret = sumArray(array);
        System.out.println(ret);
    }
    public static void main2(String[] args) {
        int [] array = {2,3,4};
        for (int i = 0; i < array.length; i++){
            array[i] = array[i] * 2;
        }
        System.out.println(Arrays.toString(array));
    }
    public static void pintArray(int [] array){
        for (int j = 0 ; j < array.length; j++){
            System.out.println(array[j]);
        }
    }
    public static void main1(String[] args) {
        int [] array = new int[100];
        for (int i = 0; i < array.length; i++) {
            array [i] = i+1;
        }
        pintArray(array);
    }
}
